package com.leetcode.ask;

import java.util.HashMap;
import java.util.Map;

public class Number76 {
    public static void main(String[] args) {
        String s = "bbaa";
        String t = "aba";
        System.out.println(minWindow(s, t));
    }

    public static String minWindow(String s, String t) {
        if (s.length() < t.length()) {
            return "";
        }
        if (s.equals(t) || s.contains(t)) {
            return t;
        }

        char[] tChars = t.toCharArray();
        Map<Character, Integer> tMap = new HashMap<>();
        for (char a : tChars) {
            if (tMap.containsKey(a)) {
                tMap.put(a, tMap.get(a) + 1);
            } else {
                tMap.put(a, 1);
            }
        }

        Map<Character, Integer> sMap = new HashMap<>();

        int l = 0;
        int r = 0;
        int lEnd = 0, rEnd = 0;
        int minLen = Integer.MAX_VALUE;
        boolean flag = false;
        char[] sCharArr = s.toCharArray();
        while (r < s.length()) {
            char sChar = sCharArr[r];
            if (tMap.containsKey(sChar)) {
                int k = sMap.getOrDefault(sChar, 0) + 1;
                sMap.put(sChar, k);
            }
            while (check(tMap, sMap) && l <= r) {
                if (minLen > r - l) {
                    minLen = r - l;
                    lEnd = l;
                    rEnd = r;
                    flag = true;
                }
                char lChar = sCharArr[l];
                if (tMap.containsKey(lChar)) {
                    int k = sMap.getOrDefault(lChar, 0) - 1;
                    sMap.put(lChar, k);
                }
                l++;
            }
            r++;

        }

        if (flag) {
            return s.substring(lEnd, rEnd + 1);
        } else {
            return "";
        }
    }

    private static boolean check(Map<Character, Integer> tMap, Map<Character, Integer> sMap) {
        for (Map.Entry entry:tMap.entrySet()){
            if (sMap.getOrDefault(entry.getKey(),0) < (int)entry.getValue()){
                return false;
            }
        }
        return true;
    }


}
